"""
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

利用辅助栈空间保持升序入栈
若是入栈时小于栈为元素就不断将后面弹出并计算面积使用当前元素填充
然后使用弹出的元素更新最大和
[2,1,5,6,2,3]
[1,1,2,2,2,3]
最大和就是 max（1*6,1*5,2*4,2*3,2*2,3*1）
"""


class Solution:
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        maxArea = 0
        for i in range(len(heights)):
            minh = s[i]
            for j in range(i,len(heights)):
                if heights[j] < minh:  minh = heights[j]
                maxArea = max(minh*(j-i+1), maxArea)
        return maxArea

    def largestRectangleArea_opt(self,heights):
        maxArea = 0
        stack = []
        for i in range(len(heights)):
            if not stack:
                stack.append(heights[i])
            elif stack[-1] <= heights[i]:
                stack.append(heights[i])
            else:
                j = i - 1
                while heights[i] < stack[j] and j >= 0:
                    maxArea = max(maxArea, stack[j] * (i - j))
                    stack[j] = heights[i]
                    j -= 1
                stack.append(heights[i])
        for i, x in enumerate(stack):
            maxArea = max(maxArea, x * (len(heights) - i))
        return maxArea

s=Solution()
print(s.largestRectangleArea_opt([2,1,5,6,2,3]))